package com.hjx.leetcode;

public class LeetCode_148r {

    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }

    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slowP = head, fastP = head.next.next;
        while (fastP != null && fastP.next != null) {
             slowP = slowP.next;
             fastP = fastP.next.next;
        }

        ListNode r = mergeSort(slowP.next);
        slowP.next = null;

        ListNode l = mergeSort(head);
        return merge(r, l);
    }

    private ListNode merge(ListNode r, ListNode l) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (r != null && l != null) {

            if (r.val < l.val) {
                cur.next = r;
                cur = cur.next;
                r = r.next;
            } else {
                cur.next = l;
                cur = cur.next;
                l = l.next;
            }
        }

        if (r == null) {
            cur.next = l;
        }

        if (l == null) {
            cur.next = r;
        }
        return dummy.next;
    }
}
